package org.example.leetcode;
import java.util.*;
/**
 * @author: lynn
 *
 * @Descript: 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * candidates 中的每个数字在每个组合中只能使用一次。
 *
 * @date: 2021/8/3 23:01
 * @version: 1.0
 */
public class LC40 {

    public static void main(String[] args) {
        LC40 lc=new LC40();
        int[] candidates=new int[]{10,1,2,7,6,1,5};
        int target=8;
        System.out.println("v:"+lc.combinationSum2v(candidates,target));
        System.out.println("i:"+lc.combinationSum2(candidates,target));
    }

    public List<List<Integer>> combinationSum2v(int[] candidates, int target) {
        List<List<Integer>> res=new ArrayList<>();
        List<Integer> list=new ArrayList<>();

        if(candidates==null || candidates.length==0){
            new ArrayList<>(res);
        }
        Arrays.sort(candidates);
        int[] v=new int[candidates.length];
        backtrack(candidates,list,res, target,v);
        return new ArrayList<>(res);
    }
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res=new ArrayList<>();
        List<Integer> list=new ArrayList<>();

        if(candidates==null || candidates.length==0){
            new ArrayList<>(res);
        }
        Arrays.sort(candidates);
        backtrack(candidates,list,res, target,0);
        return new ArrayList<>(res);
    }

    //backtrack,用 v的话， [[1, 2, 5], [1, 5, 2], [1, 7], [2, 1, 5], [2, 5, 1], [2, 6], [5, 1, 2], [5, 2, 1], [6, 2], [7, 1]]
    private void backtrack(int[] candidates,List<Integer> list,
                           List<List<Integer>> res,
                           int target,int[] v) {
        if (target==0){
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i=0;i<candidates.length;i++){
            if (candidates[i]>target) break;
            //fixme 控制输出不重复
            if (i>0 && candidates[i]==candidates[i-1]) continue;
            if (v[i]==1) continue;
            v[i]=1;
            list.add(candidates[i]);
            //fixme 通过v，使得顺序不一样也能输出
            backtrack(candidates,list,res,target-candidates[i],v);
            list.remove(list.size()-1);
            v[i]=0;
        }
    }

    private void backtrack(int[] candidates,List<Integer> list,
                           List<List<Integer>> res,
                           int target,int start) {
        if (target==0){
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i=start;i<candidates.length;i++){
            if (candidates[i]>target) break;
            //fixme 控制输出不重复
            if (i>start && candidates[i]==candidates[i-1]) continue;
            list.add(candidates[i]);
            //fixme 这里还是i+1,代表每次只用一个，这个就是39和40题的区别
            backtrack(candidates,list,res,target-candidates[i],i+1);
            list.remove(list.size()-1);

        }
    }
}
